package interview;

/**
 * 面试题 16.26. 计算器
 */
public class T1626 {
    public static void main(String[] args) {
        System.out.println(new Solution().calculate(" 3612+   52 /    21 "));
    }

static class Solution {
    public int calculate(String s) {
        int offset, length = offset = 0;
        int opIndex, syIndex = opIndex = 0;

        int[] opStack = new int[s.length() / 2 + 1]; // 操作数栈 最坏情况下（1+1）栈深度是2
        char[] syStack = new char[s.length() / 3 + 1]; // 符号栈 最坏情况下（1+2*3) 需要的栈深度为2

        for (int i = 0; i < s.length(); i++) {
            char c;
            if(isNum((c = s.charAt(i))))
                length ++;
            else { // 遇到符号
                if(c == ' ') {
                    if(offset == length){ // 跳过空格
                        offset++;
                        length = offset;
                    }
                    continue;
                }
                // 数字进入操作数栈
                opStack[opIndex ++] = getNum(s, offset, length);
                offset = i + 1; // 重新开始计算offset
                length = offset;
                while(syIndex > 0 && getPriority(c) <= getPriority(syStack[syIndex - 1])) {
                    int t = calc(syStack[--syIndex], opStack[--opIndex], opStack[--opIndex]);
                    opStack[opIndex++] = t;
                }
                syStack[syIndex++] = c; // 符号入栈
            }
        }
        // 最后一个数字进入操作数栈
        opStack[opIndex ++] = getNum(s, offset, length);
        while(syIndex > 0) {
            int t = calc(syStack[-- syIndex], opStack[-- opIndex], opStack[-- opIndex]);
            opStack[opIndex ++] = t;
        }
        return opStack[0];
    }

    /**
     * 获取数字
     * @param s
     * @param offset
     * @param length
     * @return
     */
    private int getNum(String s, int offset, int length) {
        int num = 0;
        int modulus = 1;
        for (int i = length - 1; i >= offset; i --) {
            num += (s.charAt(i) - 48) * modulus;
            modulus *= 10;
        }
        return num;
    }

    private boolean isNum(char c) {
        return c >= '0' && c <= '9';
    }

    private int calc(char symbol, int n1, int n2) {
        switch (symbol) {
            case '-': return n2 - n1;
            case '+': return n2 + n1;
            case '*': return n2 * n1;
            case '/': return n2 / n1;
        }
        return 0;
    }

    private byte getPriority(char c) {
        switch (c) {
            case '+':
            case '-': return 0;
            case '*':
            case '/': return 1;
        }
        return -1;
    }
}
}